package com.jia.leetCode;

import java.util.Arrays;

/**
 * 1356. 根据数字二进制下 1 的数目排序
 *
 */
public class Pro1356 {
    class Pair implements Comparable<Pair>{
        int num;
        int count;
        public Pair(int num, int count) {
            this.num = num;
            this.count = count;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.count != o.count) {
                return this.count - o.count;
            }else {
                return this.num - o.num;
            }
        }
    }
    public int[] sortByBits(int[] arr) {
        Pair[] ps = new Pair[arr.length];
        int index = 0;
        for(int a : arr) {
            ps[index++] = new Pair(a, countBit1(a));
        }
        Arrays.sort(ps);
        for(int i = 0; i < ps.length; i++) {
            arr[i] = ps[i].num;
        }
        return arr;
    }

    private int countBit1(int num){
        int res = 0;
        while(num != 0) {
            num &=(num - 1);
            ++res;
        }
        return res;
    }
}
